package top.whysu.study.mysql.bplustree;

public class BPlusTree {

    public static void main(String[] args) {
        System.out.println(linearSearch(171));
        System.out.println(binarySearch(249));
    }

    /**
     * 递增数组
     */
    static int[] datas = new int[]{28, 52, 103, 147, 171, 182, 198, 223, 249, 257, 278, 313, 369, 481, 532, 562};

    /**
     * 线性查找 Linear Search
     */
    public static int linearSearch(int value) {
        // 前提: datas是一个递增数组
        int index = 0;
        while (index < datas.length && datas[index] < value) {
            index++;
        }
        if (index >= datas.length || datas[index] != value) {
            return -1;
        }
        return index;
    }

    /**
     * 二分查找
     */
    public static int binarySearch(int value) {
        int start = 0;
        int end = datas.length - 1;
        while (start <= end) {
            int center = (start + end) / 2;
            if (datas[center] == value) {
                return center;
            } else if (datas[center] < value) {
                start = center + 1;
            } else {
                end = center - 1;
            }
        }
        return  -1;
    }
}
